"""
通过化简二型文法 并且将二型文法转化为GNF
基于GNF 可以实现下推自动机 PDA
"""

from CFG2GNF import getGNF
from CFG2GNF import showProductions
import collections


class PDA:

    def __init__(self, path, S):
        self.V, self.T, self.P, self.S = getGNF(path, S)
        print('开始符号', self.S)
        print('产生式:')
        showProductions(self.P)
        print('\n')

    def pushDownByProductions(self, input_str):
        """
        完全依赖GNF产生式来进行最左派生
        如果遇到二义的派生又该如何处理呢？
        比如 S->aBCD S->aBA B->b A->a C->c 现在输入abc 当处理到b时 又该推入哪个产生式呢？
        所以不确定的下推自动机只能用回溯解决二义性问题
        :param input_str:
        :return:
        """

        if not input_str:
            print('输入为空')
            return

        stack = collections.deque()
        stack.append(self.S)  # 首先开始符号压栈

        for char in input_str:
            if len(stack) == 0:  # 栈内语法成分都匹配完成了 句子还没完
                print('句子内容超出合法范围')
                return

            top = stack.pop()
            for right in self.P[top]:
                if right[0][0] == char:
                    for symbol in right[-1:0:-1]:
                        stack.append(symbol)
            else:
                # 没有找到相匹配的产生式
                print('没有找到相匹配的产生式 非法输入')
                return

        else:
            # 符号输入完毕 要检查栈内是否还有没有对应的语法成分
            if len(stack) != 0:
                print('未输入完成')
                return
            else:
                # 正常结果 句子刚好能对应所有语法成分
                print('句子合法')
                return

    def NDPA_backtracking(self, input_str):
        """
        不确定的下推自动机只能用回溯解决二义性问题
        :param input_str:
        :return:
        """
        if not input_str:
            print('输入为空')
            return

        """
        现有的是 格雷巴赫范式 和 输入的字符串
        """

        def DFS(queue, remaining_str) -> bool:
            """
            如果能成功匹配 那么应该是queue 和 str都没有剩余
            """
            print('queue:', queue, '  str:', remaining_str)
            if len(queue) == 0 and len(remaining_str) == 0:
                return True
            elif len(queue) == 0 or len(remaining_str) == 0:
                return False

            firstVar = queue[0]  # 获取需要进行的最右推到的变量（即第一个变量）
            valid_rights = []  # 符合要求可以进行推导的产生式

            for right in self.P[firstVar]:
                if right[0][0] == remaining_str[0]:
                    valid_rights.append([sym for sym, name, id, attr in right])  # 把（符号名称，名称，下标，属性）变为 符号名称 进行存储
            print('符合要求可以进行推导的产生式：', valid_rights)

            """
            例如： S->aABC | aAC  A->a  B->b C->c 现在匹配字符串aabc
            正确的是
            aabc S 可以匹配的产生式是 aABC aAC
            然后传给下一个DFS  ABC  abc
            下一个  BC bc  
            """
            for right in valid_rights:
                if DFS(right[1:] + queue[1:], remaining_str[1:]):
                    return True
            return False

        if DFS([self.S], input_str):
            print('句子符合文法')
            return True
        else:
            print('句子不符合文法')
            return False


if __name__ == '__main__':
    # pda = PDA(path='D:\\p.txt', S='S')
    pda = PDA(path='..\GNF\p4.txt', S='S')
    # p1是只要以a开头的所有ab的句子都可以
    input_str = 'daaabbb'
    pda.NDPA_backtracking(input_str)

"""
p1的句子是 a(a|b)*
p2的语言是 { 0x|x∈{0,1}* } U {0x_y|x∈{0,1}*, y∈{0，1}+} 
p3的语言是 奇数个a 或者 奇数个b
p4的句子是 da+b* 以d开头后接至少一个a然后接随意个数b
"""
